1. Field of the Invention
The present invention relates to data management and, more particularly, to the management of replicated data in a single cluster or distributed processing system. Still more particularly, the present invention relates to a system and procedure for maintaining data coherency in data replicas in either a cluster or distributed configuration.
2. Background and Related Art
Computer systems can consist of one or more computers. Distributed computer systems are created by linking a number of computer systems by a private communication mechanism, local area network (LAN) or wide area network (WAN). Each of the linked computers typically has a processor, I/O devices, volatile storage, and non-volatile storage. Certain ones of the computers are designated as "servers." A server provides services for one or more other computers which are labelled "clients." A server usually provides non-volatile (e.g. hard disk) storage that can be shared by a number of computers. Servers may also provided shared processing resources and shared access to expensive peripherals, such as high speed printers or scanners.
The sharing of data resident on a server has certain advantages for departments or workgroups with common data processing requirements. Distribution of data over a network, however, can create problems if the network or server experiences an outage. In addition, access to data over a wide area network may be costly and may have increased access times.
One approach to increasing the availability and reliability of distributed systems is to replicate data on more than one server. Thus, a particular shared data file may be replicated or copied to one or more other servers. As a result, a client may recover from failure of a server or network segment by accessing a different replica.
Replication policy can be either "optimistic" or "pessimistic." A pessimistic replication policy requires that at most one copy of the data be writable or updatable. This ensures data consistency because only one copy of the data can be changed and that copy is always assumed to be correct. Other replicas under the pessimistic policy are designated "read-only."
The pessimistic policy ensures data integrity but may result in limited availability of the updatable replica to any one of the clients. An optimistic replication policy, in contrast, allows multiple replicas to be concurrently updatable. Conflicting updates are detected and resolved after they occur. An optimistic replication policy provides higher write availability to client systems. Write sharing between users, i.e. multiple users updating multiple replicas of the same data, is assumed to be infrequent and, consequently, the impact of potential conflicts is minimized.
An optimistic replication policy, however, can lead to inconsistencies in data between replicas on different servers due to server or network failure. A technical problem exists to manage replica updates to minimize inconsistencies and to detect and resolve any inconsistencies in a timely manner.
Existing distributed file systems have been unable to provide a satisfactory solution to this problem. The Andrew File System (AFS) from Transarc Corp. and the Distributed File System (DFS) for the Distributed Computing Environment (DCE) from the Open Software Foundation (OSF) each implement replicated data with a pessimistic replication policy. AFS and DFS allow at most one updatable replica, thereby avoiding the data conflict problem, but sacrificing availability.
The CODA distributed file system, a research project developed at Carnegie Mellon University, implements an optimistic replication policy (see M. Satyanarayanan et al, "CODA: A Highly Available File System for a Distributed Workstation Environment", IEEE Transactions on Computers, Vol. 39, No. 4, April 1990.) A client system data request initiates replica update for the data. This update policy has the disadvantage of being controlled by the client, which is assumed to be untrustworthy. It is also not timely because no conflict detection occurs unless a client requests particular data. The CODA approach may also prove to be costly in cases where the communications cost for client-to-server connections is high.
Lotus Notes allows multiple read/write replicas of its special database. Replicas are periodically reconciled, usually no more than once or twice a day. Detection of a conflict between replicas causes the creation of separate versions with no attempt to automatically resolve the conflicts. This results in a significant manual management burden whenever a conflict occurs.
In a paper by Tait et al [see "Server Interface and Replica Management Algorithm for Mobile File System Clients", Computer Science Department, Columbia University], the problem of maintaining replicas in a distributed file system is investigated. The authors argue that in an environment with mobile file system clients a lazy server-based update operation should be used for replica management, and present a solution for this lazy server-based update.
Thus, the technical problem remains of creating an optimistic replication system that permits multiple updatable replicas but identifies and resolves conflicts in a timely and efficient manner.